home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / glimpse-2.1 / get_index.c < prev    next >
C/C++ Source or Header  |  1995-05-16  |  41KB  |  1,196 lines
  1. /* Copyright (c) 1994 Burra Gopal, Udi Manber.  All Rights Reserved. */
  2. #include "glimpse.h"
  3. #include "defs.h"
  4.  
  5. #if    BG_DEBUG
  6. extern    FILE    *debug;
  7. #endif    /*BG_DEBUG*/
  8. extern    char    *INDEX_DIR;
  9. extern    int    Only_first;
  10. extern    int    OneFilePerBlock;
  11. extern    int    StructuredIndex;
  12. extern    int    WHOLEFILESCOPE;
  13. extern    unsigned int dest_index_set[REAL_PARTITION];
  14. extern    unsigned char dest_index_buf[REAL_INDEX_BUF];
  15. extern    int    mask_int[32];
  16. extern    int    errno;
  17. extern    int    ByteLevelIndex;
  18. extern    int    NOBYTELEVEL;
  19. extern    int    OPTIMIZEBYTELEVEL;
  20. extern    int    RegionLimit;
  21. extern    struct offsets **src_offset_table;
  22. extern    unsigned int    multi_dest_index_set[MAXNUM_PAT][REAL_PARTITION];
  23. extern    struct offsets **multi_dest_offset_table[MAXNUM_PAT];
  24. extern    char    *index_argv[MAX_ARGS];
  25. extern    int    index_argc;
  26. extern    CHAR    GProgname[MAXNAME];
  27.  
  28. free_list(p1)
  29.     struct offsets     **p1;
  30. {
  31.     struct offsets    *tp1;
  32.  
  33.     while (*p1 != NULL) {
  34.         tp1 = *p1;
  35.         *p1 = (*p1)->next;
  36.         my_free(tp1, sizeof(struct offsets));
  37.     }
  38. }
  39.  
  40. /* Unions offset lists list2 with list1 sorted in increasing order (deletes elements from list2) => changes both list1 and list2: f += #elems added */
  41. sorted_union(list1, list2, f, pf, cf)
  42.     struct offsets **list1, **list2;
  43.     int    *f, pf, cf;
  44. {
  45.     register struct offsets **p1 = list1, *p2;
  46.     register int    count = *f;    /* don't update *f if setting NOBYTELEVEL */
  47.  
  48.     if (NOBYTELEVEL) {    /* cannot come here! */
  49.         free_list(list1);
  50.         free_list(list2);
  51.         return;
  52.     }
  53.     if ( ((pf > MIN_OCCURRENCES)  && (count > MAX_UNION * pf)) || (count > MAX_ABSOLUTE*OneFilePerBlock) ||
  54.          ((count > MIN_OCCURRENCES) && (pf > MAX_UNION * count)) || (pf > MAX_ABSOLUTE*OneFilePerBlock) ) {
  55.         /* enough if we check the second condition at the beginning since it won't surely be satisfied after this when count ++ */
  56.         NOBYTELEVEL = 1;
  57.         return;
  58.     }
  59.     while (*list2 != NULL) {
  60.         /* extract 1st element, update list2 */
  61.         p2 = *list2;
  62.         *list2 = (*list2)->next;
  63.         p2->next = NULL;
  64.  
  65.         /* find position to insert p2, and do so */
  66.         p1 = list1;
  67.         while (((*p1) != NULL) && ((*p1)->offset < p2->offset)) p1 = &(*p1)->next;
  68.         if (*p1 == NULL) {    /* end of list1: append list2 to it and return */
  69.             *p1 = p2;
  70.             p2->next = *list2;
  71.             *list2 = NULL;
  72.             if (cf > 0)  count = *f + cf;
  73.             if ( ((pf > MIN_OCCURRENCES) && (count > MAX_UNION * pf)) || (count > MAX_ABSOLUTE*OneFilePerBlock)) {
  74.                 NOBYTELEVEL = 1;
  75.                 return;
  76.             }
  77.             *f = count;
  78.             return;
  79.         }
  80.         else if (p2->offset == (*p1)->offset) my_free(p2, sizeof(struct offsets));
  81.         else {
  82.             p2->next = *p1;
  83.             *p1 = p2;
  84.             count ++;
  85.             if ( ((pf > MIN_OCCURRENCES)  && (count > MAX_UNION * pf)) || (count > MAX_ABSOLUTE*OneFilePerBlock) ) {
  86.                 NOBYTELEVEL = 1;
  87.                 return;
  88.             }
  89.             /* update list1 */
  90.             list1 = &(*p1)->next;
  91.         }
  92.     }
  93.     *f = count;
  94. }
  95.  
  96. /* Intersects offset lists list2 with list1 sorted in increasing order (deletes elements from list2) => changes both list1 and list2 */
  97. sorted_intersection(filenum, list1, list2, f)
  98.     struct offsets **list1, **list2;
  99.     int    *f;
  100. {
  101.     register struct offsets **p1 = list1, *p2, *tp1;
  102.     register int diff;
  103.  
  104.     if (NOBYTELEVEL) {    /* cannot come here! */
  105.         free_list(list1);
  106.         free_list(list2);
  107.         return;
  108.     }
  109.  
  110.     /* find position to intersect list2, and do so: REMEBER: list1 is in increasing order, and so is list2 !!! */
  111.     p1 = list1;
  112.     while ( ((*p1) != NULL) && (*list2 != NULL) ) {
  113.         diff = (*list2)->offset - (*p1)->offset;
  114.         if ( (diff >= -RegionLimit) && (diff <= RegionLimit) ) {
  115.             (*p1)->done = 1; /* p1 is in */
  116.             p1 = &(*p1)->next;
  117.             /* Can't increment p2 here since it might keep others after p1 also in */
  118.         }
  119.         else {
  120.             if (diff < 0) {
  121.                 p2 = *list2;
  122.                 *list2 = (*list2)->next;
  123.                 my_free(p2, sizeof(struct offsets));
  124.                 /* p1 can intersect with list2's next */
  125.             }
  126.             else {
  127.                 if((*p1)->done) p1 = &(*p1)->next; /* imposs */
  128.                 else {
  129.                     tp1 = *p1;
  130.                     *p1 = (*p1)->next;
  131.                     my_free(tp1, sizeof(struct offsets));
  132.                     (*f) --;
  133.                 }
  134.                 /* list2 can intersect with p1's next */
  135.             }
  136.         }
  137.     }
  138.  
  139.     while (*list2 != NULL) {
  140.         p2 = *list2;
  141.         *list2 = (*list2)->next;
  142.         my_free(p2, sizeof(struct offsets));
  143.     }
  144.  
  145.     p1 = list1;
  146.     while (*p1 != NULL) {
  147.         if ((*p1)->done == 0) {
  148.             tp1 = *p1;
  149.             *p1 = (*p1)->next;
  150.             my_free(tp1, sizeof(struct offsets));
  151.             (*f) --;
  152.         }
  153.         else {
  154.             (*p1)->done = 0;    /* for the next round! */
  155.             p1 = &(*p1)->next;
  156.         }
  157.     }
  158. }
  159.  
  160. purge_offsets(p1)
  161.     struct offsets **p1;
  162. {
  163.     struct offsets *tp1;
  164.  
  165.     while (*p1 != NULL) {
  166.         if ((*p1)->sign == 0) {
  167.             tp1 = *p1;
  168.             (*p1) = (*p1)->next;
  169.             my_free(tp1, sizeof(struct offsets));
  170.         }
  171.         else p1 = &(*p1)->next;
  172.     }
  173. }
  174.  
  175. /* Returns 1 if it is a Universal set, 0 otherwise. Constraint: WORD_END_MARK/ALL_INDEX_MARK must occur at or after buffer[0] */
  176. get_set(buffer, set, offset_table, patlen, pattern, patattr, outfile, partfp, frequency, prevfreq)
  177.     unsigned char    *buffer;
  178.     unsigned int    *set;
  179.     struct offsets **offset_table;
  180.     int    patlen;
  181.     char    *pattern;
  182.     int    patattr;
  183.     FILE    *outfile;
  184.     FILE    *partfp;
  185.     int    *frequency, prevfreq;
  186. {
  187.     int    bdx2, j;
  188.     int    ret;
  189.     int    x=0, y=0, diff, even_words=1, prevy;
  190.     int    indexattr = 0;
  191.     struct offsets *o, *tailo, *heado;
  192.     int    delim = encode8b(0);
  193.     int    curfreq = 0;
  194.  
  195.     /* buffer[0] is '\n', search must start from buffer[1] */
  196.     if (StructuredIndex) {
  197.         if (StructuredIndex < MaxNum8bPartition - 1) {
  198.             indexattr = decode8b(buffer[1]);
  199.             bdx2 = 2;
  200.         }
  201.         else if (StructuredIndex < MaxNum16bPartition - 1) {
  202.             indexattr = decode16b((buffer[1] << 8) | buffer[2]);
  203.             bdx2 = 3;
  204.         }
  205.         else {
  206.             indexattr = decode32b((buffer[1] << 24) | (buffer[2] << 16) | (buffer[3] << 8) | (buffer[4]));
  207.             bdx2 = 5;
  208.         }
  209.         /* printf("i=%d p=%d\n", indexattr, patattr); */
  210.  
  211.         if ((patattr > 0) && (indexattr != patattr)) {
  212. #if    BG_DEBUG
  213.             fprintf(debug, "indexattr=%d DOES NOT MATCH patattr=%d\n", indexattr, patattr);
  214. #endif    /*BG_DEBUG*/
  215.             return 0;
  216.         }
  217.         /* else, pat_attr is 0 => everything, OR, attribute matches */
  218.     }
  219.     else bdx2 = 1;
  220.  
  221.     if (OneFilePerBlock)
  222.         while((bdx2<REAL_INDEX_BUF+1) && (buffer[bdx2] != WORD_END_MARK) && (buffer[bdx2] != ALL_INDEX_MARK)) bdx2++;
  223.     else while((bdx2<REAL_INDEX_BUF+1) && (buffer[bdx2] != WORD_END_MARK)) bdx2++;
  224.     if (bdx2 >= REAL_INDEX_BUF+1) return 0;
  225.     if (OneFilePerBlock && (buffer[bdx2] == ALL_INDEX_MARK)) {
  226.         /* A intersection Univ-set = A: so src_index_set won't change; A union Univ-set = Univ-set: so src_index_set = all 1s */
  227. #if    BG_DEBUG
  228.         buffer[bdx2] = '\0';
  229.         fprintf(debug, "All indices search for %s\n", buffer + 1);
  230.         buffer[bdx2] = ALL_INDEX_MARK;
  231. #endif    /*BG_DEBUG*/
  232.         set[REAL_PARTITION - 1] = 1;
  233.         for(bdx2=0; bdx2<round(OneFilePerBlock, 8*sizeof(int)) - 1; bdx2++) {
  234.             set[bdx2] = 0xffffffff;
  235.         }
  236.         set[bdx2] = 0;
  237.         for (j=0; j<8*sizeof(int); j++) {
  238.             if (bdx2*8*sizeof(int) + j >= OneFilePerBlock) break;
  239.             set[bdx2] |= mask_int[j];
  240.         }
  241.         if (ByteLevelIndex) NOBYTELEVEL = 1;
  242.         return 1;
  243.     }
  244.     else if (!OneFilePerBlock) {    /* check only if index+partitions are NOT split */
  245. #if    BG_DEBUG
  246.         buffer[bdx2] = '\0';
  247.         fprintf(debug, "memagrep-line: %s\t\tpattern: %s\n", buffer, pattern);
  248. #endif    /*BG_DEBUG*/
  249.         /* ignore if pattern with all its options matches block number sequence: bg+udi: Feb/16/93 */
  250.         buffer[bdx2] = '\n';    /* memagrep needs buffer to end with '\n' */
  251.         if ((ret = memagrep_search(patlen, pattern, bdx2+1, buffer, 0, outfile)) <= 0) return 0;
  252.         else buffer[bdx2] = WORD_END_MARK;
  253.     }
  254.     bdx2++;    /* bdx2 now points to the first byte of the offset */
  255.  
  256.     even_words = 1;
  257.     /* Code identical to that in merge_in() in glimpseindex */
  258.     if (OneFilePerBlock) {
  259.         get_block_numbers(&buffer[bdx2], &buffer[bdx2], partfp);
  260.         while((bdx2<REAL_INDEX_BUF) && (buffer[bdx2] != '\n') && (buffer[bdx2] != '\0')) {
  261.         /* First get the file name */
  262.         x = 0;
  263.         if (ByteLevelIndex) {
  264.             if (OneFilePerBlock <= MaxNum8bPartition) {
  265.             x = decode8b(buffer[bdx2]);
  266.             bdx2 ++;
  267.             }
  268.             else {
  269.             x = (buffer[bdx2] << 8) | buffer[bdx2+1];
  270.             x = decode16b(x);
  271.             bdx2 += 2;
  272.             }
  273.         }
  274.         else if (OneFilePerBlock <= MaxNum8bPartition) {
  275.             x = decode8b(buffer[bdx2]);
  276.             bdx2 ++;
  277.         }
  278.         else if (OneFilePerBlock <= MaxNum12bPartition) {
  279.             if (even_words) {
  280.             x = ((buffer[bdx2+1] & 0x0000000f) << 8) | buffer[bdx2];
  281.             x = decode12b(x);
  282.             bdx2 += 2;
  283.             even_words = 0;
  284.             }
  285.             else {    /* odd number of words so far */
  286.             x = ((buffer[bdx2-1] & 0x000000f0) << 4) | buffer[bdx2];
  287.             x = decode12b(x);
  288.             bdx2 ++;
  289.             even_words = 1;
  290.             }
  291.         }
  292.         else if (OneFilePerBlock <= MaxNum16bPartition) {
  293.             x = (buffer[bdx2] << 8) | buffer[bdx2+1];
  294.             x = decode16b(x);
  295.             bdx2 += 2;
  296.         }
  297.         set[block2index(x)] |= block2mask(x);
  298.  
  299.         prevy = 0;
  300.         if (ByteLevelIndex) {
  301.             heado = tailo = NULL;
  302.             curfreq = 0;
  303.             while ((bdx2<REAL_INDEX_BUF) && (buffer[bdx2] != '\n') && (buffer[bdx2] != '\0')) {
  304.             y = decode8b(buffer[bdx2]);
  305.             if ((y & 0x000000c0) == 0) {    /* one byte offset */
  306.                 diff = y&0x0000003f;
  307.                 y = prevy + diff;
  308.                 bdx2 ++;
  309.             }
  310.             else if ((y & 0x000000c0) == 0x40) {    /* two byte offset */
  311.                 diff = decode8b(buffer[bdx2+1]);
  312.                 y = prevy + (((y & 0x0000003f) * MaxNum8bPartition) + diff);
  313.                 bdx2 += 2;
  314.             }
  315.             else if ((y & 0x000000c0) == 0x80) {    /* three byte offset */
  316.                 diff = decode16b((buffer[bdx2+1] << 8) | buffer[bdx2+2]);
  317.                 y = prevy + (((y & 0x0000003f) * MaxNum16bPartition) + diff);
  318.                 bdx2 += 3;
  319.             }
  320.             else {    /* four byte offset */
  321.                 diff = decode24b((buffer[bdx2+1] << 16) | (buffer[bdx2+2] << 8) | buffer[bdx2+3]);
  322.                 y = prevy + (((y & 0x0000003f) * MaxNum24bPartition) + diff);
  323.                 bdx2 += 4;
  324.             }
  325.             prevy = y;
  326.  
  327.             curfreq ++;
  328.  
  329.             if (!Only_first && !NOBYTELEVEL &&    /* below borrowed from sorted_union */
  330.                 !(((prevfreq>MIN_OCCURRENCES)&&(curfreq+*frequency>MAX_UNION*prevfreq)) || (curfreq+*frequency>MAX_ABSOLUTE*OneFilePerBlock))) {
  331.                 /* These o's will be in sorted order. Just collect all of them and merge with &offset_table[x]. */
  332.                 o = (struct offsets *)my_malloc(sizeof(struct offsets));
  333.                 o->offset = y;
  334.                 o->next = NULL;
  335.                 o->sign = o->done = 0;
  336.                 if (heado == NULL) {
  337.                 heado = o;
  338.                 tailo = o;
  339.                 }
  340.                 else {
  341.                 tailo->next = o;
  342.                 tailo = o;
  343.                 }
  344.             }
  345.             else {
  346.                 if (heado != NULL) free_list(&heado);
  347.                 /* printf("1 "); */
  348.                 NOBYTELEVEL = 1;    /* can't return since have to or the bitmasks */
  349.             }
  350.             if ((bdx2<REAL_INDEX_BUF) && (buffer[bdx2] == delim)) {    /* look at offsets corr. to a new file now */
  351.                 bdx2 ++;
  352.                 break;
  353.             }
  354.             }
  355.  
  356.             if (heado == NULL) *frequency += curfreq;
  357.             else if (!Only_first && !NOBYTELEVEL) {
  358.             sorted_union(&offset_table[x], &heado, frequency, prevfreq, curfreq);    /* this will free heado's elements and ++ *frequency */
  359.             if (NOBYTELEVEL) *frequency += curfreq;    /* can't return since have to or the bitmasks */
  360.             if (heado != NULL) free_list(&heado);
  361.             }
  362.         }
  363.         }
  364.     }
  365.     else {
  366.         while((bdx2<MAX_INDEX_BUF) && (buffer[bdx2] != '\n') && (buffer[bdx2] != '\0') && (buffer[bdx2] < MAX_PARTITION)) {
  367.         set[buffer[bdx2]] = 1;
  368.         bdx2++;
  369.         }
  370.     }
  371.  
  372.     return 0;
  373. }
  374.  
  375. /*
  376.  * This is a very simple function: it gets the list of matched lines from the index,
  377.  * and sets the block numbers corr. to files that need to be searched in "index_tab".
  378.  * It also sets the file-offsets that have to be searched in "offset_tab" (byte-level).
  379.  */
  380. get_index(infile, index_tab, offset_tab, pattern, patlen, patattr, index_argv, index_argc, outfile, partfp, parse, first_time)
  381. char *infile;
  382. unsigned int  *index_tab;
  383. struct offsets **offset_tab;
  384. char *pattern;
  385. int patlen;
  386. int patattr;
  387. char *index_argv;
  388. int index_argc;
  389. FILE *outfile;
  390. FILE *partfp;
  391. int parse;
  392. int first_time;
  393. {
  394.     int  i=0, j, iii;
  395.     FILE *f_in;
  396.     struct offsets **offsetptr = multi_dest_offset_table[0];
  397.     int ret=0;
  398.  
  399.     if (OneFilePerBlock && (parse & OR_EXP) && (index_tab[REAL_PARTITION - 1] == 1)) return 0;
  400.     if((f_in = fopen(infile, "r")) == NULL) {
  401.         fprintf(stderr, "%s: can't open for reading: %s/%s\n", GProgname, INDEX_DIR, infile);
  402.         return -1;
  403.     }
  404.     if (OneFilePerBlock)
  405.         for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) {
  406.                 dest_index_set[i] = 0;
  407.         }
  408.     else for(i=0; i<MAX_PARTITION; i++) {
  409.                 dest_index_set[i] = 0;
  410.         }
  411.     dest_index_buf[0] = '\n';    /* memagrep needs buffer to begin with '\n' */
  412.  
  413.     dest_index_set[REAL_PARTITION - 2] = 0;
  414.     while(fgets(dest_index_buf+1, REAL_INDEX_BUF, f_in)) {
  415. #if    BG_DEBUG
  416.         fprintf(debug, "index-line: %s", dest_index_buf+1);
  417. #endif    /*BG_DEBUG*/
  418.         if ((ret = get_set(&dest_index_buf[0], dest_index_set, offsetptr, patlen, pattern, patattr, outfile, partfp, &dest_index_set[REAL_PARTITION - 2], index_tab[REAL_PARTITION - 2])) != 0)
  419.             break;    /* all index mark touched */
  420.     }
  421.     if (NOBYTELEVEL) {
  422.         for (iii=0; iii<OneFilePerBlock; iii++) {
  423.         free_list(&offset_tab[iii]);
  424.         free_list(&offsetptr[iii]);
  425.         }
  426.     }
  427.  
  428.     /* Take intersection if parse=ANDPAT or 0 (one terminal pattern), union if OR_EXP; Take care of universal sets in offset_tab[REAL_PARTITION - 1] */
  429.     if (OneFilePerBlock) {
  430.         if (parse & OR_EXP) {
  431.         if (ret) {
  432.         ret_is_1:
  433.             index_tab[REAL_PARTITION - 1] = 1;
  434.             for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)) - 1; i++) {
  435.             index_tab[i] = 0xffffffff;
  436.             }
  437.             index_tab[i] = 0;
  438.             for (j=0; j<8*sizeof(int); j++) {
  439.             if (i*8*sizeof(int) + j >= OneFilePerBlock) break;
  440.             index_tab[i] |= mask_int[j];
  441.             }
  442.             if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) for (i=0; i<OneFilePerBlock; i++) {
  443.             free_list(&offsetptr[i]);
  444.             free_list(&offset_tab[i]);
  445.             }
  446.             if (ByteLevelIndex) NOBYTELEVEL = 1;
  447.             fclose(f_in);
  448.             return 0;
  449.         }
  450.         index_tab[REAL_PARTITION - 1] = 0;
  451.         for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) index_tab[i] |= dest_index_set[i];
  452.         if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) {
  453.             for (i=0; i<OneFilePerBlock; i++) {
  454.             sorted_union(&offset_tab[i], &offsetptr[i], &index_tab[REAL_PARTITION - 2], dest_index_set[REAL_PARTITION - 2], 0);
  455.             if (NOBYTELEVEL) {
  456.                 for (iii=0; iii<OneFilePerBlock; iii++) {
  457.                 free_list(&offset_tab[iii]);
  458.                 free_list(&offsetptr[iii]);
  459.                 }
  460.                 break;
  461.             }
  462.             }
  463.         }
  464.         }
  465.         else {
  466.         if (((index_tab[REAL_PARTITION - 1] == 1) || first_time) && (ret)) {
  467.         both_are_1:
  468.             if (first_time) {
  469.             index_tab[REAL_PARTITION - 1] = 1;
  470.             for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)) - 1; i++) {
  471.                 index_tab[i] = 0xffffffff;
  472.             }
  473.             index_tab[i] = 0;
  474.             for (j=0; j<8*sizeof(int); j++) {
  475.                 if (i*8*sizeof(int) + j >= OneFilePerBlock) break;
  476.                 index_tab[i] |= mask_int[j];
  477.             }
  478.             }
  479.             first_time = 0;
  480.             if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) for (i=0; i<OneFilePerBlock; i++) {
  481.             free_list(&offsetptr[i]);
  482.             free_list(&offset_tab[i]);
  483.             }
  484.             if (ByteLevelIndex) NOBYTELEVEL = 1;
  485.             /*
  486.             fclose(f_in);
  487.             return 0;
  488.             */
  489.         }
  490.         else if ((index_tab[REAL_PARTITION - 1] == 1) || first_time) {
  491.             first_time = 0;
  492.             index_tab[REAL_PARTITION - 1] = 0;
  493.             for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) index_tab[i] = dest_index_set[i];
  494.             if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) {
  495.             for (i=0; i<OneFilePerBlock; i++) {
  496.                 free_list(&offset_tab[i]);
  497.                 offset_tab[i] = offsetptr[i];
  498.                 offsetptr[i] = NULL;
  499.             }
  500.             }
  501.         }
  502.         else if (ret) {
  503.             if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) for (i=0; i<OneFilePerBlock; i++) free_list(&offsetptr[i]);
  504.         }
  505.         else {
  506.             for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) index_tab[i] &= dest_index_set[i];
  507.             if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) {
  508.             if (first_time || WHOLEFILESCOPE) {
  509.                 first_time = 0;
  510.                 for (i=0; i<OneFilePerBlock; i++) {
  511.                 sorted_union(&offset_tab[i], &offsetptr[i], &index_tab[REAL_PARTITION - 2], dest_index_set[REAL_PARTITION - 2], 0);
  512.                 if (NOBYTELEVEL) {
  513.                     for (iii=0; iii<OneFilePerBlock; iii++) {
  514.                     free_list(&offset_tab[iii]);
  515.                     free_list(&offsetptr[iii]);
  516.                     }
  517.                     break;
  518.                 }
  519.                 }
  520.             }
  521.             else {
  522.                 for (i=0; i<OneFilePerBlock; i++) {
  523.                 if ((index_tab[block2index(i)] & mask_int[i % (8*sizeof(int))]))
  524.                     sorted_intersection(i, &offset_tab[i], &offsetptr[i], &index_tab[REAL_PARTITION - 2]);
  525.                 else free_list(&offsetptr[i]);
  526.                 /*
  527.                 if (index_tab[REAL_PARTITION - 2] < MIN_OCCURRENCES) {
  528.                     if (!NOBYTELEVEL) {
  529.                         for (iii=0; iii<OneFilePerBlock; iii++) {
  530.                         free_list(&offset_tab[iii]);
  531.                         free_list(&offsetptr[iii]);
  532.                         }
  533.                     }
  534.                     NOBYTELEVEL = 1;
  535.                     OPTIMIZEBYTELEVEL = 1;
  536.                     break;
  537.                 }
  538.                 */
  539.                 }
  540.             }
  541.             }
  542.         }
  543.         }
  544.     }
  545.     else {
  546.         if (parse & OR_EXP)
  547.         for(i=0; i<MAX_PARTITION; i++) index_tab[i] |= dest_index_set[i];
  548.         else
  549.         for(i=0; i<MAX_PARTITION; i++) index_tab[i] &= dest_index_set[i];
  550.     }
  551.  
  552. #if    BG_DEBUG
  553.     fprintf(debug, "get_index(): the following partitions are ON\n");
  554.     for(i=0; i<((OneFilePerBlock > 0) ? round(OneFilePerBlock, 8*sizeof(int)) : MAX_PARTITION); i++) {
  555.           if(index_tab[i]) fprintf(debug, "%d,%x\n", i, index_tab[i]);
  556.     }
  557. #endif    /*BG_DEBUG*/
  558.  
  559.     fclose(f_in);
  560.     return 0;
  561. }
  562.  
  563. /*
  564.  * Same as above, but uses mgrep to search the index for many patterns at one go,
  565.  * and interprets the output obtained from the -M and -P options (set in main.c).
  566.  */
  567. mgrep_get_index(infile, index_tab, offset_tab, pat_list, pat_lens, pat_attr, mgrep_pat_index, num_mgrep_pat, patbufpos, index_argv, index_argc, outfile, partfp, parse, first_time)
  568. char *infile;
  569. int  *index_tab;
  570. struct offsets **offset_tab;
  571. char *pat_list[];
  572. int pat_lens[];
  573. int pat_attr[];
  574. int mgrep_pat_index[];
  575. int num_mgrep_pat;
  576. int patbufpos;
  577. char *index_argv[];
  578. int index_argc;
  579. FILE *outfile;
  580. FILE *partfp;
  581. int parse;
  582. int first_time;
  583. {
  584.     int  i=0, j, temp, iii, jjj;
  585.     FILE *f_in;
  586.     int ret;
  587.     int x=0, y=0, even_words=1;
  588.     int patnum;
  589.     unsigned int *setptr;
  590.     struct offsets **offsetptr;
  591.     CHAR dummypat[MAX_PAT];
  592.     int  dummylen=0;
  593.     char  allindexmark[MAXNUM_PAT];
  594.     int k;
  595.     int sorted[MAXNUM_PAT], min, max;
  596.  
  597.     if (OneFilePerBlock && (parse & OR_EXP) && (index_tab[REAL_PARTITION - 1] == 1)) return 0;
  598.     /* Do the mgrep() */
  599.     if ((f_in = fopen(infile, "w")) == NULL) {
  600.         fprintf(stderr, "%s: run out of file descriptors!\n", GProgname);
  601.         return -1;
  602.     }
  603.     errno = 0;
  604.     if ((ret = fileagrep(index_argc, index_argv, 0, f_in)) < 0) {
  605.         fprintf(stderr, "%s: error in searching index\n", GProgname);
  606.         fclose(f_in);
  607.         return -1;
  608.     }
  609.     fflush(f_in);
  610.     fclose(f_in);
  611.     f_in = NULL;
  612.  
  613.     index_argv[patbufpos] = NULL;
  614.     /* For index-search with memgrep and get-filenames */
  615.     dummypat[0] = '\0';
  616.     if ((dummylen = memagrep_init(index_argc, index_argv, MAX_PAT, dummypat)) <= 0) {
  617.         fclose(f_in);
  618.         return -1;
  619.     }
  620.  
  621.     /* Interpret the result */
  622.     if((f_in = fopen(infile, "r")) == NULL) {
  623.         fprintf(stderr, "%s: can't open for reading: %s/%s\n", GProgname, INDEX_DIR, infile);
  624.         return -1;
  625.     }
  626.     if (OneFilePerBlock) {
  627.         for (patnum=0; patnum<num_mgrep_pat; patnum ++) {
  628.         for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) {
  629.             multi_dest_index_set[patnum][i] = 0;
  630.         }
  631.         if (ByteLevelIndex) for(i=0; i<OneFilePerBlock; i++) {
  632.             multi_dest_offset_table[patnum][i] = NULL;
  633.         }
  634.         multi_dest_index_set[patnum][REAL_PARTITION - 1] = 0;
  635.         multi_dest_index_set[patnum][REAL_PARTITION - 2] = 0;
  636.         }
  637.     }
  638.     else {
  639.         for (patnum=0; patnum<num_mgrep_pat; patnum ++)
  640.         for(i=0; i<MAX_PARTITION; i++) {
  641.                     multi_dest_index_set[patnum][i] = 0;
  642.         }
  643.     }
  644.     dest_index_buf[0] = '\n';    /* memagrep needs buffer to begin with '\n' */
  645.  
  646.     memset(allindexmark, '\0', num_mgrep_pat);
  647.     min = (index_tab[REAL_PARTITION - 1] == 1) ? 0 : index_tab[REAL_PARTITION - 2];
  648.     while(fgets(dest_index_buf+1, REAL_INDEX_BUF, f_in)) {
  649.         patnum=0;
  650.         sscanf(&dest_index_buf[1], "%d-", &patnum);
  651. #if    BG_DEBUG
  652.         fprintf(debug, "patnum=%d len=%d pat=%s attr=%d index-line: %s\n", patnum, pat_lens[mgrep_pat_index[patnum-1]], pat_list[mgrep_pat_index[patnum-1]], pat_attr[mgrep_pat_index[patnum-1]], dest_index_buf+1);
  653. #endif    /*BG_DEBUG*/
  654.         if ((patnum < 1) || (patnum > num_mgrep_pat)) continue;    /* error! */
  655.         setptr = multi_dest_index_set[patnum - 1];
  656.         offsetptr = multi_dest_offset_table[patnum - 1];
  657.         for(k=0; dest_index_buf[k] != ' '; k++);
  658.         dest_index_buf[k] = '\n';
  659.         if (!allindexmark[patnum - 1])
  660.             allindexmark[patnum - 1] = (char)get_set(&dest_index_buf[k], setptr, offsetptr, pat_lens[mgrep_pat_index[patnum-1]],
  661.                                 pat_list[mgrep_pat_index[patnum-1]], pat_attr[mgrep_pat_index[patnum-1]], outfile, partfp,
  662.                                 &setptr[REAL_PARTITION - 2], min);
  663.         /* To test the maximum disparity to stop unions within above */
  664.         if (!allindexmark[patnum-1]) min = setptr[REAL_PARTITION - 2];
  665.         for (patnum=0; patnum<num_mgrep_pat; patnum ++) {
  666.             if ((multi_dest_index_set[patnum][REAL_PARTITION - 2] < min) && (multi_dest_index_set[patnum][REAL_PARTITION - 1] != 1))
  667.                 min = multi_dest_index_set[patnum][REAL_PARTITION - 2];
  668.         }
  669.         min += (index_tab[REAL_PARTITION - 1] == 1) ? 0 : index_tab[REAL_PARTITION - 2];
  670.     }
  671. #if    0
  672.     for (patnum=0; patnum<num_mgrep_pat; patnum++)
  673.         printf("%d=%d,%d\n", patnum, multi_dest_index_set[patnum][REAL_PARTITION - 1], multi_dest_index_set[patnum][REAL_PARTITION - 2]);
  674. #endif    /*0*/
  675.  
  676.     for (patnum=0; patnum<num_mgrep_pat; patnum++)
  677.         sorted[patnum] = patnum;
  678.     if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) {
  679.         max = 0;
  680.         for (patnum=1; patnum<num_mgrep_pat; patnum++) {
  681.             if (multi_dest_index_set[patnum][REAL_PARTITION - 2] > multi_dest_index_set[max][REAL_PARTITION - 2])
  682.             max = patnum;
  683.         }
  684.         /* Sort them according to the lengths of the lists in increasing order: min first */
  685.         for (patnum=0; patnum<num_mgrep_pat; patnum++) {
  686.             min = patnum;
  687.             for (j=patnum+1; j<num_mgrep_pat; j++)
  688.             if (multi_dest_index_set[sorted[j]][REAL_PARTITION - 2] < multi_dest_index_set[sorted[min]][REAL_PARTITION - 2])
  689.                 min = j;
  690.             if (min != patnum) {
  691.             temp = sorted[patnum];
  692.             sorted[patnum] = sorted[min];
  693.             sorted[min] = temp;
  694.             }
  695.         }
  696.         if (multi_dest_index_set[sorted[max]][REAL_PARTITION - 2] > MAX_DISPARITY * multi_dest_index_set[sorted[0]][REAL_PARTITION - 2]) {
  697.             NOBYTELEVEL = 1;
  698.             /* printf("4 "); */
  699.             for (iii=0; iii<OneFilePerBlock; iii++) {
  700.             for (jjj=0; jjj<num_mgrep_pat; jjj++)
  701.                 free_list(&multi_dest_offset_table[jjj][iii]);
  702.             free_list(&offset_tab[iii]);
  703.             }
  704.         }
  705.     }
  706.     else if (NOBYTELEVEL) {
  707.         for (iii=0; iii<OneFilePerBlock; iii++) {
  708.         for (jjj=0; jjj<num_mgrep_pat; jjj++)
  709.             free_list(&multi_dest_offset_table[jjj][iii]);
  710.         free_list(&offset_tab[iii]);
  711.         }
  712.     }
  713.  
  714.     /* Take intersection if parse=ANDPAT or 0 (one terminal pattern), union if OR_EXP; Take care of universal sets in offset_tab[REAL_PARTITION - 1] */
  715.     for (patnum=0; patnum<num_mgrep_pat; patnum++) {
  716.         if (OneFilePerBlock) {
  717.             if (parse & OR_EXP) {
  718.             if (allindexmark[sorted[patnum]]) {
  719.             ret_is_1:
  720.                 index_tab[REAL_PARTITION - 1] = 1;
  721.                 for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)) - 1; i++) {
  722.                 index_tab[i] = 0xffffffff;
  723.                 }
  724.                 index_tab[i] = 0;
  725.                 for (j=0; j<8*sizeof(int); j++) {
  726.                 if (i*8*sizeof(int) + j >= OneFilePerBlock) break;
  727.                 index_tab[i] |= mask_int[j];
  728.                 }
  729.                 if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) for (patnum=0;patnum<num_mgrep_pat;patnum++) for (i=0; i<OneFilePerBlock; i++) {
  730.                 free_list(&multi_dest_offset_table[sorted[patnum]][i]);
  731.                 free_list(&offset_tab[i]);
  732.                 }
  733.                 if (ByteLevelIndex) NOBYTELEVEL = 1;
  734.                 fclose(f_in);
  735.                 return 0;
  736.             }
  737.             index_tab[REAL_PARTITION - 1] = 0;
  738.             for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) index_tab[i] |= multi_dest_index_set[sorted[patnum]][i];
  739.             if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) {
  740.                 for (i=0; i<OneFilePerBlock; i++) {
  741.                 sorted_union(&offset_tab[i], &multi_dest_offset_table[sorted[patnum]][i], &index_tab[REAL_PARTITION - 2], multi_dest_index_set[sorted[patnum]][REAL_PARTITION - 2], 0);
  742.  
  743.                 if (NOBYTELEVEL) {
  744.                     for (iii=0; iii<OneFilePerBlock; iii++) {
  745.                     for (jjj=0; jjj<num_mgrep_pat; jjj++)
  746.                         free_list(&multi_dest_offset_table[jjj][iii]);
  747.                     free_list(&offset_tab[iii]);
  748.                     }
  749.                     break;
  750.                 }
  751.                 }
  752.             }
  753.             }
  754.             else {
  755.             if (((index_tab[REAL_PARTITION - 1] == 1) || first_time) && (allindexmark[sorted[patnum]])) {
  756.             both_are_1:
  757.                 if (first_time) {
  758.                 index_tab[REAL_PARTITION - 1] = 1;
  759.                 for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)) - 1; i++) {
  760.                     index_tab[i] = 0xffffffff;
  761.                 }
  762.                 index_tab[i] = 0;
  763.                 for (j=0; j<8*sizeof(int); j++) {
  764.                     if (i*8*sizeof(int) + j >= OneFilePerBlock) break;
  765.                     index_tab[i] |= mask_int[j];
  766.                 }
  767.                 }
  768.                 first_time = 0;
  769.                 if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) for (patnum=0;patnum<num_mgrep_pat;patnum++) for (i=0; i<OneFilePerBlock; i++) {
  770.                  free_list(&multi_dest_offset_table[sorted[patnum]][i]);
  771.                  free_list(&offset_tab[i]);
  772.                 }
  773.                 if (ByteLevelIndex) NOBYTELEVEL = 1;
  774.                 /*
  775.                 fclose(f_in);
  776.                 return 0;
  777.                 */
  778.             }
  779.             else if ((index_tab[REAL_PARTITION - 1] == 1) || first_time) {
  780.                 first_time = 0;
  781.                 index_tab[REAL_PARTITION - 1] = 0;
  782.                 for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) index_tab[i] = multi_dest_index_set[sorted[patnum]][i];
  783.                 if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) {
  784.                 for (i=0; i<OneFilePerBlock; i++) {
  785.                     free_list(&offset_tab[i]);
  786.                     offset_tab[i] = multi_dest_offset_table[sorted[patnum]][i];
  787.                     multi_dest_offset_table[sorted[patnum]][i] = NULL;
  788.                 }
  789.                 }
  790.             }
  791.             else if (allindexmark[sorted[patnum]]) {
  792.                 if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) for (i=0; i<OneFilePerBlock; i++) free_list(&multi_dest_offset_table[sorted[patnum]][i]);
  793.             }
  794.             else {
  795.                 for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) index_tab[i] &= multi_dest_index_set[sorted[patnum]][i];
  796.                 if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) {
  797.                 if (first_time || WHOLEFILESCOPE) {
  798.                     first_time = 0;
  799.                     for (i=0; i<OneFilePerBlock; i++) {
  800.                     sorted_union(&offset_tab[i], &multi_dest_offset_table[sorted[patnum]][i], &index_tab[REAL_PARTITION - 2], multi_dest_index_set[sorted[patnum]][REAL_PARTITION - 2], 0);
  801.                     if (NOBYTELEVEL) {
  802.                         for (iii=0; iii<OneFilePerBlock; iii++) {
  803.                         for (jjj=0; jjj<num_mgrep_pat; jjj++)
  804.                             free_list(&multi_dest_offset_table[jjj][iii]);
  805.                         free_list(&offset_tab[iii]);
  806.                         }
  807.                         break;
  808.                     }
  809.                     }
  810.                 }
  811.                 else {
  812.                     for (i=0; i<OneFilePerBlock; i++) {
  813.                     if ((index_tab[block2index(i)] & mask_int[i % (8*sizeof(int))]))
  814.                         sorted_intersection(i, &offset_tab[i], &multi_dest_offset_table[sorted[patnum]][i], &index_tab[REAL_PARTITION - 2]);
  815.                     else free_list(&multi_dest_offset_table[sorted[patnum]][i]);
  816.                     /*
  817.                     if (index_tab[REAL_PARTITION - 2] < MIN_OCCURRENCES) {
  818.                         if (!NOBYTELEVEL) {
  819.                             for (iii=0; iii<OneFilePerBlock; iii++) {
  820.                             for (jjj=0; jjj<num_mgrep_pat; jjj++)
  821.                                 free_list(&multi_dest_offset_table[jjj][iii]);
  822.                             free_list(&offset_tab[iii]);
  823.                             }
  824.                         }
  825.                         NOBYTELEVEL = 1;
  826.                         OPTIMIZEBYTELEVEL = 1;
  827.                         break;
  828.                     }
  829.                     */
  830.                     }
  831.                 }
  832.                 }
  833.             }
  834.             }
  835.         }
  836.         else {
  837.             if (parse & OR_EXP) {
  838.             for (patnum=0; patnum<num_mgrep_pat; patnum++)
  839.                 for(i=0; i<MAX_PARTITION; i++) index_tab[i] |= multi_dest_index_set[patnum][i];
  840.             }
  841.             else {
  842.             for (patnum=0; patnum<num_mgrep_pat; patnum++)
  843.                 for(i=0; i<MAX_PARTITION; i++) index_tab[i] &= multi_dest_index_set[patnum][i];
  844.             }
  845.         }
  846.     }
  847.  
  848. #if    BG_DEBUG
  849.     fprintf(debug, "get_index(): the following partitions are ON\n");
  850.     for(i=0; i<((OneFilePerBlock > 0) ? round(OneFilePerBlock, 8*sizeof(int)) : MAX_PARTITION); i++) {
  851.           if(index_tab[i]) fprintf(debug, "%d,%x\n", i, index_tab[i]);
  852.     }
  853. #endif    /*BG_DEBUG*/
  854.  
  855.     fclose(f_in);
  856.     return 0;
  857. }
  858.  
  859. /* All borrowed from main.c and are needed for searching the index */
  860. extern    CHAR    *pat_list[MAXNUM_PAT];  /* complete words within global pattern */
  861. extern    int    pat_lens[MAXNUM_PAT];   /* their lengths */
  862. extern    int    pat_attr[MAXNUM_PAT];   /* set of attributes */
  863. extern    int    num_pat;
  864. extern    CHAR    pat_buf[(MAXNUM_PAT + 2)*MAXPAT];
  865. extern    int    pat_ptr;
  866. extern    int    is_mgrep_pat[MAXNUM_PAT];
  867. extern    int    mgrep_pat_index[MAXNUM_PAT];
  868. extern    int    num_mgrep_pat;
  869. extern    unsigned int    src_index_set[REAL_PARTITION];
  870. extern    struct offsets **src_offset_table;
  871. extern    struct offsets **curr_offset_table;
  872. extern    char    tempfile[];
  873. extern    int    patindex;
  874. extern    int    patbufpos;
  875. extern    ParseTree terminals[MAXNUM_PAT];
  876. extern    int    INVERSE;    /* agrep's global: need here to implement ~ in index-search */
  877. extern    int    GBESTMATCH;        /* Should I change -B to -# where # = no. of errors? */
  878. extern    int    bestmatcherrors;    /* set during index search, used later on */
  879. extern    FILE    *partfp;        /* glimpse partitions */
  880. extern    FILE    *nullfp;        /* to discard output: agrep -s doesn't work properly */
  881. extern    int    ComplexBoolean;
  882. extern    int    num_terminals;
  883.  
  884. /* Returns the number of times a successful search was conducted: unused info at present. */
  885. fillup_target(result_index_set, result_offset_table, parse)
  886.     unsigned int    result_index_set[REAL_PARTITION];
  887.     struct offsets **result_offset_table;
  888.     int    parse;
  889. {
  890.     int    i=0;
  891.     FILE    *tmpfp;
  892.     int    dummylen = 0;
  893.     char    dummypat[MAX_PAT];
  894.     int    successes = 0, ret;
  895.     int    first_time = 1;
  896.  
  897.     while (i < num_pat)  {
  898.         if (is_mgrep_pat[i] && (num_mgrep_pat > 1)) {    /* do later */
  899.             i++;
  900.             continue;
  901.         }
  902.         strcpy(index_argv[patindex], pat_list[i]);    /* i-th pattern in its right position */
  903.         /* printf("pat_list[%d] = %s\n", i, pat_list[i]); */
  904.  
  905.         if ((tmpfp = fopen(tempfile, "w")) == NULL) {
  906.             fprintf(stderr, "%s: cannot open for writing: %s, errno=%d\n", GProgname, tempfile, errno);
  907.             return(-1);
  908.         }
  909.         errno = 0;
  910.  
  911.         /* If this is the glimpse server, since the process doesn't die, most of its data pages might still remain in memory */
  912.         if ((ret = fileagrep(index_argc, index_argv, 0, tmpfp)) < 0) {
  913.             /* reinitialization here takes care of agrep_argv changes AFTER split_pattern */
  914.             fprintf(stderr, "%s: error in searching index\n", GProgname);
  915.             fclose(tmpfp);
  916.             return(-1);
  917.         }
  918.         /* Now, the output of index search is in tempfile: need to use files here since index is too large */
  919.         fflush(tmpfp);
  920.         fclose(tmpfp);
  921.         tmpfp = NULL;
  922.  
  923.         /* Keep track of the maximum number of errors */
  924.         if (GBESTMATCH) {
  925.             if (errno > bestmatcherrors)
  926.                 bestmatcherrors = errno;
  927.         }
  928.  
  929.         /* At this point, all index-search options are properly set due to the above fileagrep */
  930.         if (-1 == get_index(tempfile, result_index_set, result_offset_table, pat_list[i], pat_lens[i], pat_attr[i], index_argv, index_argc, nullfp, partfp, parse, first_time))
  931.             return(-1);
  932.         successes ++;
  933.         first_time = 0;
  934.         i++;
  935.     }
  936.     fflush(stderr);
  937.  
  938.     /* For index-search with memgrep in mgrep_get_index, and get-filenames */
  939.     dummypat[0] = '\0';
  940.     if ((dummylen = memagrep_init(index_argc, index_argv, MAX_PAT, dummypat)) <= 0) return(-1);
  941.     if (num_mgrep_pat > 1) {
  942.         CHAR *old_buf = (CHAR *)index_argv[patbufpos];    /* avoid my_free and re-my_malloc */
  943.         index_argv[patbufpos] = (char*)pat_buf;    /* this contains all the patterns with the right -m and -M options */
  944. #if    BG_DEBUG
  945.         fprintf(debug, "pat_buf = %s\n", pat_buf);
  946. #endif    /*BG_DEBUG*/
  947.         strcpy(index_argv[patindex], "-z");    /* no-op: patterns are in patbufpos; also avoid shift-left of index_argv */
  948.         if (-1 == mgrep_get_index(tempfile, result_index_set, result_offset_table,
  949.                 pat_list, pat_lens, pat_attr, mgrep_pat_index, num_mgrep_pat, patbufpos,
  950.                 index_argv, index_argc, nullfp, partfp, parse, first_time)) {
  951.             index_argv[patbufpos] = (char *)old_buf;    /* else will my_free array! */
  952.             fprintf(stderr, "%s: error in searching index\n", GProgname);
  953.             return(-1);
  954.         }
  955.         successes ++;
  956.         first_time = 0;
  957.         index_argv[patbufpos] = (char *)old_buf;
  958.     }
  959.  
  960.     return successes;
  961. }
  962.  
  963. /*
  964.  * Now, I search the index by doing an in-order traversal of the boolean parse tree starting at GParse.
  965.  * The results at each node are stored in src_offset_table and src_index_set. Before the right child is
  966.  * evaluated, results of the left child are stored in curr_offset_table and curr_index_set (accumulators)
  967.  * and are unioned/intersected/noted with the right child's results (which get stored in src_...) and
  968.  * passed on above. The accumulators are allocated at each internal node and freed after evaluation.
  969.  * Left to right evaluation is good since number of curr_offset_tables that exist simultaneously depends
  970.  * entirely on the maximum depth of a right branch (REAL_PARTITION is small so it won't make a difference).
  971.  */
  972. int
  973. search_index(tree)
  974.     ParseTree *tree;
  975. {
  976.     int    prev_INVERSE;
  977.     int    i, j, iii;
  978.     int    first_time = 0;    /* since it is used AFTER left child has been computed */
  979.     unsigned int    curr_index_set[REAL_PARTITION];
  980.     struct offsets **curr_offset_table = NULL;
  981.  
  982.     if (ComplexBoolean) {    /* recursive */
  983.         if (tree == NULL) return -1;
  984.         if (tree->type == LEAF) {
  985.             /* always AND pat of individual words at each term: initialize accordingly */
  986.             if (OneFilePerBlock) {
  987.                 for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) src_index_set[i] = 0xffffffff;
  988.             }
  989.             else for(i=0; i<MAX_PARTITION; i++) src_index_set[i] = 1;
  990.             src_index_set[REAL_PARTITION - 1] = 0;
  991.             src_index_set[REAL_PARTITION - 2] = 0;
  992.  
  993.             if (split_terminal(tree->terminalindex, tree->terminalindex+1) <= 0) return -1;
  994.             prev_INVERSE = INVERSE;    /* agrep's global to implement NOT */
  995.             if (tree->op & NOTPAT) INVERSE = 1;
  996.             if (fillup_target(src_index_set, src_offset_table, AND_EXP) <= 0) return -1;
  997.             INVERSE = prev_INVERSE;
  998.             return 1;
  999.         }
  1000.         else if (tree->type == INTERNAL) {
  1001.             /* Search the left node and see if the right node can be searched */
  1002.             if (search_index(tree->data.internal.left) <= 0) return -1;
  1003.             if (OneFilePerBlock && ((tree->op & OPMASK) == ORPAT) && (src_index_set[REAL_PARTITION - 1] == 1)) goto quit;    /* nothing to do */
  1004.             if ((tree->data.internal.right == NULL) || (tree->data.internal.right->type == 0)) return -1;    /* uninitialized: see main.c */
  1005.  
  1006.             /* Save previous src_index_set and src_offset_table in fresh accumulators */
  1007.             if (OneFilePerBlock) {
  1008.                 memcpy(curr_index_set, src_index_set, round(OneFilePerBlock,8));
  1009.                 curr_index_set[REAL_PARTITION - 1] = src_index_set[REAL_PARTITION - 1];
  1010.                 src_index_set[REAL_PARTITION - 1] = 0;
  1011.                 curr_index_set[REAL_PARTITION - 2] = src_index_set[REAL_PARTITION - 2];
  1012.                 src_index_set[REAL_PARTITION - 2] = 0;
  1013.             }
  1014.             else memcpy(curr_index_set, src_index_set, MAX_PARTITION * sizeof(int));
  1015.             if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) {
  1016.                 if ((curr_offset_table = (struct offsets **)malloc(sizeof(struct offsets *) * OneFilePerBlock)) == NULL) {
  1017.                     fprintf(stderr, "%s: malloc failure at: %s:%d\n", GProgname, __FILE__, __LINE__);
  1018.                     return -1;
  1019.                 }
  1020.                 memcpy(curr_offset_table, src_offset_table, OneFilePerBlock * sizeof(struct offsets *));
  1021.                 memset(src_offset_table, '\0', sizeof(struct offsets *) * OneFilePerBlock);
  1022.             }
  1023.  
  1024.             /* Now evaluate the right node which automatically put the results in src_index_set/src_offset_table */
  1025.             if (search_index(tree->data.internal.right) <= 0) {
  1026.                 if (curr_offset_table != NULL) free(curr_offset_table);
  1027.                 return -1;
  1028.             }
  1029.  
  1030.             /*
  1031.              * Alpha substitution of the code in get_index():
  1032.              * index_tab <- src_index_set
  1033.              * dest_index_table <- curr_index_set
  1034.              * offset_tab <- src_offset_table
  1035.              * dest_offset_table <- curr_offset_table
  1036.              * ret <- src_index_set[REAL_PARTITION - 1] for ORPAT, curr_index_set for ANDPAT
  1037.              * frequency = src_index_set[REAL_PARTITION - 2] in both ORPAT and ANDPAT
  1038.              * first_time <- 0
  1039.              * return 0 <- goto quit
  1040.              * Slight difference since we want the results to go to src rather than curr.
  1041.              */
  1042.             if (OneFilePerBlock) {
  1043.                 if ((tree->op & OPMASK) == ORPAT) {
  1044.                 if (src_index_set[REAL_PARTITION - 1] == 1) {    /* curr..[..] can never be 1 since we would have quit above itself */
  1045.                 ret_is_1:
  1046.                     src_index_set[REAL_PARTITION - 1] = 1;
  1047.                     for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)) - 1; i++) {
  1048.                     src_index_set[i] = 0xffffffff;
  1049.                     }
  1050.                     src_index_set[i] = 0;
  1051.                     for (j=0; j<8*sizeof(int); j++) {
  1052.                     if (i*8*sizeof(int) + j >= OneFilePerBlock) break;
  1053.                     src_index_set[i] |= mask_int[j];
  1054.                     }
  1055.                     if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) for (i=0; i<OneFilePerBlock; i++) {
  1056.                     free_list(&curr_offset_table[i]);
  1057.                     free_list(&src_offset_table[i]);
  1058.                     }
  1059.                     if (ByteLevelIndex) NOBYTELEVEL = 1;
  1060.                     goto quit;
  1061.                 }
  1062.                 src_index_set[REAL_PARTITION - 1] = 0;
  1063.                 for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) src_index_set[i] |= curr_index_set[i];
  1064.                 if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) {
  1065.                     for (i=0; i<OneFilePerBlock; i++) {
  1066.                     sorted_union(&src_offset_table[i], &curr_offset_table[i], &src_index_set[REAL_PARTITION - 2], curr_index_set[REAL_PARTITION - 2], 0);
  1067.                     if (NOBYTELEVEL) {
  1068.                         for (iii=0; iii<OneFilePerBlock; iii++) {
  1069.                         free_list(&src_offset_table[iii]);
  1070.                         free_list(&curr_offset_table[iii]);
  1071.                         }
  1072.                         break;
  1073.                     }
  1074.                     }
  1075.                 }
  1076.                 }
  1077.                 else {
  1078.                 if (((src_index_set[REAL_PARTITION - 1] == 1) || first_time) && (curr_index_set[REAL_PARTITION - 1] == 1)) {
  1079.                 both_are_1:
  1080.                     if (first_time) {
  1081.                     src_index_set[REAL_PARTITION - 1] = 1;
  1082.                     for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)) - 1; i++) {
  1083.                         src_index_set[i] = 0xffffffff;
  1084.                     }
  1085.                     src_index_set[i] = 0;
  1086.                     for (j=0; j<8*sizeof(int); j++) {
  1087.                         if (i*8*sizeof(int) + j >= OneFilePerBlock) break;
  1088.                         src_index_set[i] |= mask_int[j];
  1089.                     }
  1090.                     }
  1091.                     first_time = 0;
  1092.                     if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) for (i=0; i<OneFilePerBlock; i++) {
  1093.                     free_list(&curr_offset_table[i]);
  1094.                     free_list(&src_offset_table[i]);
  1095.                     }
  1096.                     if (ByteLevelIndex) NOBYTELEVEL = 1;
  1097.                     /*
  1098.                     goto quit;
  1099.                     */
  1100.                 }
  1101.                 else if ((src_index_set[REAL_PARTITION - 1] == 1) || first_time) {
  1102.                     first_time = 0;
  1103.                     src_index_set[REAL_PARTITION - 1] = 0;
  1104.                     for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) src_index_set[i] = curr_index_set[i];
  1105.                     if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) {
  1106.                     for (i=0; i<OneFilePerBlock; i++) {
  1107.                         free_list(&src_offset_table[i]);
  1108.                         src_offset_table[i] = curr_offset_table[i];
  1109.                         curr_offset_table[i] = NULL;
  1110.                     }
  1111.                     }
  1112.                 }
  1113.                 else if (curr_index_set[REAL_PARTITION - 1] == 1) {
  1114.                     if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) for (i=0; i<OneFilePerBlock; i++) free_list(&curr_offset_table[i]);
  1115.                 }
  1116.                 else {
  1117.                     for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) src_index_set[i] &= curr_index_set[i];
  1118.                     if (ByteLevelIndex && !NOBYTELEVEL && !Only_first) {
  1119.                     if (first_time || WHOLEFILESCOPE) {
  1120.                         first_time = 0;
  1121.                         for (i=0; i<OneFilePerBlock; i++) {
  1122.                         sorted_union(&src_offset_table[i], &curr_offset_table[i], &src_index_set[REAL_PARTITION - 2], curr_index_set[REAL_PARTITION - 2], 0);
  1123.                         if (NOBYTELEVEL) {
  1124.                             for (iii=0; iii<OneFilePerBlock; iii++) {
  1125.                             free_list(&src_offset_table[iii]);
  1126.                             free_list(&curr_offset_table[iii]);
  1127.                             }
  1128.                             break;
  1129.                         }
  1130.                         }
  1131.                     }
  1132.                     else {
  1133.                         for (i=0; i<OneFilePerBlock; i++) {
  1134.                         if ((src_index_set[block2index(i)] & mask_int[i % (8*sizeof(int))]))
  1135.                             sorted_intersection(i, &src_offset_table[i], &curr_offset_table[i], &src_index_set[REAL_PARTITION - 2]);
  1136.                         else free_list(&curr_offset_table[i]);
  1137.                         /*
  1138.                         if (src_index_set[REAL_PARTITION - 2] < MIN_OCCURRENCES) {
  1139.                             if (!NOBYTELEVEL) {
  1140.                                 for (iii=0; iii<OneFilePerBlock; iii++) {
  1141.                                 free_list(&src_offset_table[iii]);
  1142.                                 free_list(&curr_offset_table[iii]);
  1143.                                 }
  1144.                             }
  1145.                             NOBYTELEVEL = 1;
  1146.                             OPTIMIZEBYTELEVEL = 1;
  1147.                             break;
  1148.                         }
  1149.                         */
  1150.                         }
  1151.                     }
  1152.                     }
  1153.                 }
  1154.                 }
  1155.             }
  1156.             else {
  1157.                 if ((tree->op & OPMASK) == ORPAT)
  1158.                 for(i=0; i<MAX_PARTITION; i++) src_index_set[i] |= curr_index_set[i];
  1159.                 else
  1160.                 for(i=0; i<MAX_PARTITION; i++) src_index_set[i] &= curr_index_set[i];
  1161.             }
  1162.  
  1163.         quit:
  1164.             if (curr_offset_table != NULL) free(curr_offset_table);
  1165.             /* Now if it is a NOT expression, complement the indices stuff knowing that it cannot be ByteLevelIndex */
  1166.             if (tree->op & NOTPAT) {
  1167.                 if (ByteLevelIndex) {
  1168.                     /* Can't recover the discarded offsets */
  1169.                     fprintf(stderr, "%s: can't handle NOT of AND/OR terms with ByteLevelIndex: please simplify the query\n", GProgname);
  1170.                     return -1;
  1171.                 }
  1172.                 if (OneFilePerBlock)
  1173.                     for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) src_index_set[i] = ~src_index_set[i];
  1174.                 else
  1175.                     for(i=0; i<MAX_PARTITION; i++) src_index_set[i] = (src_index_set[i] ? 0 : 1);
  1176.             }
  1177.         }
  1178.         else return -1;
  1179.     }
  1180.     else {    /* iterative just as it is now: initialize */
  1181.         if ((int)tree & OR_EXP) memset(src_index_set, '\0', round(OneFilePerBlock,8));
  1182.         else {
  1183.             if (OneFilePerBlock) for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) src_index_set[i] = 0xffffffff;
  1184.             else for(i=0; i<MAX_PARTITION; i++) src_index_set[i] = 1;
  1185.         }
  1186.         src_index_set[REAL_PARTITION - 1] = 0;
  1187.         src_index_set[REAL_PARTITION - 2] = 0;
  1188.  
  1189.         if (split_terminal(0, num_terminals) <= 0) return -1;
  1190.         if (fillup_target(src_index_set, src_offset_table, (int)tree) <= 0) return -1;
  1191.     }
  1192.  
  1193.     return 1;
  1194. }
  1195.  
  1196.